/*
 * graphe.cpp
 *
 *  Created on: 3 juin 2009
 *      Author: hissel
 */

#include 	<fstream>
#include 	<sstream>
#include	<iostream>
#include	<vector>
#include	<list>
#include	<algorithm>
#include	<cfloat>
#include	<functional>
#include	<string>
#include 	"graphe.h"
#include	"heap.h"


/**********************************************/
/* FONCTIONS DIVERSES UTILISEES PAR LE MODULE */
/**********************************************/
/**
 * \struct Arclist
 * Structure de liste d'arcs simplifiée, utilisée pour l'algorithme d'optimisation de tournée
 * 
 * La structure n'est disponible que dans le module local. Elle n'est pas destinée à être appelée de l'extérieur. Elle permet de stocker une liste de pointeurs vers des arcs sous une forme légère et simplifiée et de permettre des opérations rapides sur ces données.
 */
struct Arclist {
	Arc* arc;	//!< Pointeur vers l'arc contenu dans la liste
	Arclist *next;	//!< Pointeur vers l'élément suivant
	Arclist(Arc *parc,Arclist *pnext):arc(parc),next(pnext) {}	//!< Constructeur standard
	~Arclist() {delete next;}	//!< Destructeur standard
	void to_list(list<Arc*> &result) {result.push_back(arc);if (next!=0) next->to_list(result);}	//!< Conversion en une liste de la bibliothèque C++
};

/**
 * \fn tournee_rec(int nombre,Sommet *debut,double lval,Arclist *&result,double &lmin)
 * \brief Composante récursive de l'algorithme de calcul de la tournée optimale
 *
 * La fonction calcule les longueurs de toutes les tournées passant par nombre éléments depuis le sommet debut, et qui n'ont pas encore été visités (vérifié par la propriété Sommet::statut). Elle détermine le chemin de longueur minimale et, si celui-ci a une longueur inférieure à lmin, place la liste des arcs qui le compose en tête de la variable result. La longueur du plus court chemin trouvé est placée dans la variable lmin. Si aucun chemin n'a pu être trouvé, lmin prend la valeur -1.
 * \param nombre Nombre de sommets à parcourir sur le chemin
 * \param debut Sommet initial du chemin
 * \param lval Longueur du chemin avant le noeud courant
 * \param result Chemin de longueur minimale trouvé jusqu'à présent
 * \param lmin Longueur minimale trouvée jusqu'à présent, DBL_MAX si on n'a rien trouvé
 */
void tournee_rec(int nombre,Sommet *debut,double lval,Arclist *&result,double &lmin) {
	if (nombre==0) {	//Initialisation de la récursivité, on a fini la tournée
		delete result;
		result=0;
		lmin=lval;
		return;
	}
	double min=lmin;	//Longueur minimale des chemins parcourus
	Arclist *res;	//Liste des arcs du plus court chemin trouvé
	debut->statut=1;
	for (list<Arc*>::iterator it=debut->arcs.begin();it!=debut->arcs.end();it++) {
		if (!(*it)->coupe && (*it)->dest->statut==0 && lval+(*it)->poids<lmin) {	//On ne parcourt la branche que si on n'a pas déjà dépassé la longueur minimale, si le sommet suivant n'a pas encore été visité, et bien sûr si l'arc n'est pas coupé
			res=result;
			tournee_rec(nombre-1,(*it)->dest,lval+(*it)->poids,res,min);
			if (min<lmin) {	//Le chemin est plus court que le meilleur trouvé jusqu'à présent, on met à jour le meilleur chemin
				lmin=min;
				result=new Arclist((*it),res);
			}
		}
	}
	if (result==0) {	//On n'a pas trouvé de chemin, soit parce qu'il n'y en avait pas de meilleur, soit parce qu'on est resté bloqué quelque part
		lmin=DBL_MAX;
	}
	debut->statut=0;
}

/***********************************************/
/* IMPLEMENTATION DE LA CLASSE GRAPHEEXCEPTION */
/***********************************************/
const char* GrapheException::what() const throw() {
	switch (code) {
		case NO_VERTEX:return ("Sommet non trouvé : "+message).c_str();
		case NO_EDGE:return ("Arête non trouvée : "+message).c_str();
		default:return message.c_str();
	}
}

/**************************************/
/* IMPLEMENTATION DE LA CLASSE SOMMET */
/**************************************/
Sommet* Sommet::voisin(const Arc* a) const {
	if (a->orig==this) return a->dest;
	else if (a->dest==this) return a->orig;
	else throw GrapheException(GrapheException::NO_VERTEX);
}

void Sommet::affiche(ostream& out) const {
	out << "Sommet " << id << " : " << nom << ", dist(" << dist << ")";
}

int compare_sommets(const void *a,const void *b,void *param) {
	if (((Sommet*)a)->dist<((Sommet*)b)->dist) return -1;
	if (((Sommet*)a)->dist>((Sommet*)b)->dist) return 1;
	return 0;
}

/***********************************/
/* IMPLEMENTATION DE LA CLASSE ARC */
/***********************************/
void Arc::affiche(ostream& out) const {
	out << "Arc " << id << " (" << orig->id << "," << dest->id << "," << poids << ") : " << nom;
}

/**************************************/
/* IMPLEMENTATION DE LA CLASSE GRAPHE */
/**************************************/
Graphe::~Graphe() {
	vide();
}

void Graphe::vide() {
	for (vector<Sommet*>::iterator it=sommets.begin();it!=sommets.end();it++) delete (*it);
	for (vector<Arc*>::iterator it=arcs.begin();it!=arcs.end();it++) delete (*it);
	sommets.clear();
	arcs.clear();
}

void Graphe::lecture(char *filename,bool oriente) {
	vide();	//Initialisation du graphe et destruction du contenu si nécessaire
	ifstream file(filename);
	bool stop=false;
	//Lecture de la liste des sommets. Chaque ligne prend la forme :
	//	index_du_sommet nom_du_sommet
	//La lecture s'arrête lorsque la ligne contient une étoile comme premier caractère. Les lignes vides sont ignorées.
	string line;
	while (!file.eof() && !stop) {
		getline(file,line);
		if (line.length()==0) continue;
		if (line.length()>0 && line[0]=='*') {
			stop=true;
			continue;
		}
		istringstream iss(line);
		int id;
		string nom;
		iss >> id >> nom;
		Sommet *s=new Sommet(id,nom);
		sommets.push_back(s);
	}
	sort(sommets.begin(),sommets.end(),Sommet::compare);	//Tri de la liste des sommets, nécessaire pour la recherche accélérée par dichotomie
	//Lecture de la liste des arcs. Chaque ligne prend la forme :
	//	index_arc debut fin poids nom_arc
	//Les lignes vides sont ignorées. La lecture s'arrête à la fin du fichier
	stop=false;
	while (!file.eof() && !stop) {
		getline(file,line);
		if (line.length()==0) continue;
		istringstream iss(line);
		int id,s1,s2;
		double p;
		string nom;
		iss >> id >> s1 >> s2 >> p >> nom;
		Sommet *ss1,*ss2;
		ss1=cherche(s1);
		ss2=cherche(s2);
		if (ss1==0 || ss2==0) throw GrapheException(GrapheException::NO_VERTEX);
		Arc *a=new Arc(id,ss1,ss2,p,nom);
		arcs.push_back(a);
		ss1->arcs.push_back(a);
		if (!oriente) {
			Arc *a2=new Arc(-id,ss2,ss1,p,nom);
			arcs.push_back(a2);
		   	ss2->arcs.push_back(a2);
		}
	}
	sort(arcs.begin(),arcs.end(),Arc::compare);
	file.close();
}

Sommet* Graphe::cherche(int pid) const {
	int a=0;
	int b=sommets.size()-1;
	int c;
	if (b<a || sommets[a]->id>pid || sommets[b]->id<pid) return 0;
	while (b>a+1) {
		if (sommets[a]->id==pid) return sommets[a];
		if (sommets[b]->id==pid) return sommets[b];
		c=(a+b)/2;
		if (sommets[c]->id>pid) b=c; else a=c;
	}
	if (sommets[a]->id==pid) return sommets[a];
	if (sommets[b]->id==pid) return sommets[b];
	return 0;
}

void Graphe::sp_iteration(Sommet *fin,Heap<Sommet*,Comparateur> &visites,double (*heuristique)(const Sommet *a,const Sommet *b)) {
	//Recherche du sommet le plus proche de l'ensemble des sommets traités. On montre par récurrence que la distance calculée pour ce sommet est bien la distance minimale. Le sommet est alors considéré comme traité et rajouté à l'ensemble.
	//Dans ce cas, statut vaut 0 si le sommet n'a pas encore été visité, 1 s'il a été traité et la distance minimale a été calculée, et 2 si le sommet appartient à la liste ouverte
	Sommet* actuel=visites.pop();
	actuel->statut=1;
	//Mise à jour des distances de tous les sommets accessibles par un arc depuis le sommet de poids minimal
	for (list<Arc*>::iterator it=actuel->arcs.begin();it!=actuel->arcs.end();it++) if ((*it)->dest->statut!=1 && !((*it)->coupe)) {
		double ndist=(*it)->poids+actuel->dist;
		if ((*it)->dest->statut==0) visites.insert((*it)->dest);
		(*it)->dest->statut=2;
		if ((*it)->dest->dist<0.0 || (*it)->dest->dist>ndist) {
			HeapNode<Sommet*,Comparateur> *hn=visites.find((*it)->dest);
			(*it)->dest->dist=ndist;
			(*it)->dest->fdist=ndist+heuristique((*it)->dest,fin);
			(*it)->dest->prec=(*it);
			if (hn!=0) visites.adjust(hn);
		}
	}
}

list<Arc*> Graphe::itineraire(Sommet *orig,Sommet *fin,double (*heuristique)(const Sommet *a,const Sommet *b)) {
	list<Arc*> result;
	if (orig==0 || fin==0) return result;
	//Initialisation de la liste des sommets
	for (vector<Sommet*>::iterator it=sommets.begin();it!=sommets.end();it++) {
		(*it)->dist=-1.0;
		(*it)->statut=0;
	}
	orig->dist=0.0;
	orig->fdist=heuristique(orig,fin);
	//Création du tas et parcours du graphe
	Heap<Sommet*,Comparateur> visites;
	visites.insert(orig);
	while (!visites.empty()) {
		if (visites.peek()==fin) {	//L'algorithme a trouvé le plus court chemin. Il retourne la liste reconstituée des sommets qui composent l'itinéraire en la créant à partir de la fin.
			Sommet* actuel=fin;
			while (actuel!=orig) {
				result.push_front((Arc*)(actuel->prec));
				actuel=((Arc*)(actuel->prec))->orig;
			}
			return result;
		}
		sp_iteration(fin,visites,heuristique);
	}
	return result;	//Si on atteint cette ligne, l'itinéraire n'a pas pu être trouvé et la liste renvoyée est donc vide.
}

void Graphe::dijkstra_graphe(list<Sommet*> &origines) {
	if (origines.size()==0) return;
	Heap<Sommet*,Comparateur> visites;
	//Initialisation des statuts et distances des sommets.
	for (vector<Sommet*>::iterator it=sommets.begin();it!=sommets.end();it++) {
		(*it)->dist=-1.0;
		(*it)->statut=0;
		(*it)->prec=0;
	}
	for (list<Sommet*>::iterator it=origines.begin();it!=origines.end();it++) {
		(*it)->dist=0.0;
		(*it)->fdist=0.0;
		visites.insert(*it);
		(*it)->statut=1;
		(*it)->prec=0;
	}
	//Parcours du réseau et écriture des distances
	while (!visites.empty()) {
		sp_iteration(0,visites);
	}
}

void Graphe::desserte(list<Sommet*> &origines) {
	if (origines.size()==0) return;
	//Appel d'un algorithme de Dijkstra sur le graphe pour calculer les distances à tous les sommets
	dijkstra_graphe(origines);
	//Initialisation du statut des sommets, 1 si le prédécesseur a déjà été mis à jour, 0 sinon
	//Initialisation des prédécesseurs des sommets d'origine par eux-mêmes
	for (vector<Sommet*>::iterator it=sommets.begin();it!=sommets.end();it++) {
		(*it)->statut=0;
	}
	for (list<Sommet*>::iterator it=origines.begin();it!=origines.end();it++) {
		(*it)->statut=1;
		(*it)->prec=(*it);
	}
	//A partir des sources, on recherche tous les sommets dont le prédécesseur a déjà été mis à jour
	//parcours contient tous les sommets déjà traités
	list<Sommet*> parcours;
	for (list<Sommet*>::iterator it=origines.begin();it!=origines.end();it++) {
		parcours.push_back(*it);
	}
	while (!parcours.empty()) {
		Sommet *s=parcours.front();
		parcours.pop_front();
		for (list<Arc*>::iterator itt=s->arcs.begin();itt!=s->arcs.end();itt++) {
			if ((*itt)->dest->statut==0 && (*itt)->dest->prec==(*itt)) {
				(*itt)->dest->statut=1;
				(*itt)->dest->prec=s->prec;
				parcours.push_back((*itt)->dest);
			}
		}
	}
	for (vector<Sommet*>::iterator it=sommets.begin();it!=sommets.end();it++) {
		if ((*it)->statut==0) (*it)->prec=0;
	}
}

list<Arc*> Graphe::tournee(Sommet *node) {
	for (vector<Sommet*>::iterator it=sommets.begin();it!=sommets.end();it++) (*it)->statut=0;
	Arclist *res=0;
	double min=DBL_MAX;
	tournee_rec(sommets.size()-1,node,0,res,min);
	list<Arc*> best;
	if (res!=0) res->to_list(best);
	delete res;
	return best;
}

